package leetcode.N201_N300;

public class N224 {


    public static void main(String[] args) {

        System.out.println(calculate("(1+(4+5+2)-3)+(6+8)"));

    }


    static int calculate(String s) {
        int [] a = new int[s.length()];
        int aIndex = 0;
        char [] b = new char[s.length()];
        int bIndex = 0;
        boolean needCalculate = false;
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            // 空格就忽略
            if (temp == ' ') {
                continue;
            }
            // 如果是数字 则遍历后面的元素 直到不是数字为止
            if (isNum(temp)) {
                int num = temp - 48;
                for (int k = i + 1; k < s.length(); k++) {
                    char kTemp = s.charAt(k);
                    if (isNum(kTemp)) {
                        num = num * 10 + (kTemp - 48);
                        i = k;
                    } else {
                        break;
                    }
                }
                // 如果是第二个数字就需要计算
                if (needCalculate) {
                    int result = doCalculate(num, a[--aIndex], b[--bIndex]);
                    a[aIndex++] = result;
                    continue;
                } else {
                    a[aIndex++] = num;
                    needCalculate = true;
                    continue;
                }
            }

            // 如果是计算操作符号 获取上一个元素
            // 1.没有上一个元素 把当前符号放入
            // 2.如果上一个元素是左括号 把当前符号放入
            // 3.如果上一个元素是计算操作符 则先计算上一个值 再把当前符号放入
            // 4.上一个元素不可能是右括号
            if (isOperation(temp)) {
                // 如果没有元素 或者 上一个元素是左括弧 直接将当前操作符 插入到操作符栈中
                if (bIndex == 0 || isLeftBrackets(b[bIndex - 1])) {
                    b[bIndex++] = temp;
                    continue;
                }
                // 上一个符号就是操作符 开始计算
                int result = doCalculate(a[--aIndex], a[--aIndex], b[--bIndex]);
                a[aIndex++] = result;
                b[bIndex++] = temp;
            }

            // 如果是左括弧 直接放入
            if (isLeftBrackets(temp)) {
                b[bIndex++] = temp;
                // 加入左括弧后 遇到的第一个数字不能计算
                needCalculate = false;
            }

            // 如果是右括弧 计算前面的值 并且把左括弧去除
            if (isRightBrackets(temp)) {
                // 提取上一个操作符
                char o = b[--bIndex];
                // 如果是左括号 则清楚左括号 其实游标已经左移等于是清除了
                if (isLeftBrackets(o)) {
                    // 清除左括号后有两种可能
                    // 1.左边没有东西了 直接返回
                    // 2.左边是一个操作符 那么就需要再计算一次
                    if (bIndex == 0) {
                        continue;
                    } else {
                        int result = doCalculate(a[--aIndex], a[--aIndex], b[--bIndex]);
                        a[aIndex++] = result;
                        continue;
                    }
                }
                // 非左括号 就是操作符 进行计算
                int result = doCalculate(a[--aIndex], a[--aIndex], b[--bIndex]);
                a[aIndex++] = result;
                // 把左括号删除
                bIndex--;
            }
        }
        return a[0];
    }

    static int doCalculate(int right, int left, char c) {
        if (c == '+') {
            return right + left;
        }
        return left - right;
    }


    static boolean isNum(char c) {
        return '0' <= c && c <= '9';
    }

    static boolean isOperation(char c) {
        return '-' == c || '+' == c;
    }

    static boolean isLeftBrackets(char c) {
        return '(' == c;
    }

    static boolean isRightBrackets(char c) {
        return ')' == c;
    }

}
